package leetcode100

// TODO 脑筋急转弯 【-】 比特位计数
// TODO https://leetcode.cn/problems/counting-bits/solution/ke-yi-shi-xiao-gai-bi-te-wei-ji-shu-goti-622v/

func countBits(n int) []int {
	//将1的个数放入输入的切片中
	abc := make([]int, n+1)
	for i := range abc {
		abc[i] = count1(i)
	}
	return abc
}

// 求 1 的个数
func count1(x int) (y int) {
	//&运算中1&1=1,1&0=0,0&0=0
	for ; x > 0; x &= x - 1 {
		y++
	}
	return y
}
